#include <iostream>
#include <sys/time.h>
#include <arm_neon.h>

using namespace std;

float a[2048][2048];

void init(int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            a[i][j] = float(rand()) / 10;
        }
    }
}

void SequentialAlgorithm(int N) {
    for (int k = 0; k < N; k++) {
        for (int j = k + 1; j < N; j++) {
            a[k][j] /= a[k][k];
        }
        a[k][k] = 1.0;

        for (int i = k + 1; i < N; i++) {
            for (int j = k + 1; j < N; j++) {
                a[i][j] -= a[i][k] * a[k][j];
            }
            a[i][k] = 0;
        }
    }
}

void AlignedParallelAlgorithm(int N) {
    float32x4_t t0, t1, t2, t3;

    for (int k = 0; k < N; k++) {
        t0 = vld1q_dup_f32(a[k] + k);

        int j;
        for (j = k + 1; j < N; j++) {
            if (((size_t)(a[k] + j)) % 16 == 0) {
                break;
            }
            a[k][j] /= a[k][k];
        }
        for (; j + 3 < N; j += 4) {
            t1 = vld1q_f32(a[k] + j);
            t2 = vdivq_f32(t1, t0);
            vst1q_f32(a[k] + j, t2);
        }
        for (; j < N; j++) {
            a[k][j] /= a[k][k];
        }

        a[k][k] = 1.0;

        for (int i = k + 1; i < N; i++) {
            t0 = vld1q_dup_f32(a[i] + k);

            for (j = k + 1; j < N; j++) {
                if (((size_t)(a[i] + j)) % 16 == 0) {
                    break;
                }
                a[i][j] -= a[i][k] * a[k][j];
            }
            for (; j + 3 < N; j += 4) {
                t1 = vld1q_f32(a[k] + j);
                t2 = vld1q_f32(a[i] + j);
                t3 = vmulq_f32(t0, t1);
                t2 = vsubq_f32(t2, t3);
                vst1q_f32(a[i] + j, t2);
            }
            for (; j < N; j++) {
                a[i][j] -= a[i][k] * a[k][j];
            }
            a[i][k] = 0.0;
        }
    }
}

int main() {
    timeval start, stop;
    double durationTime;

    for (int N = 64; N <= 2048; N += 64) {
        cout << "Testing matrix size: " << N << endl;

        init(N);
        gettimeofday(&start, NULL);
        SequentialAlgorithm(N);
        gettimeofday(&stop, NULL);
        durationTime = (stop.tv_sec - start.tv_sec) * 1000.0 + (stop.tv_usec - start.tv_usec) / 1000.0;
        cout << "SequentialAlgorithm time: " << durationTime << " ms" << endl;

        init(N);
        gettimeofday(&start, NULL);
        AlignedParallelAlgorithm(N);
        gettimeofday(&stop, NULL);
        durationTime = (stop.tv_sec - start.tv_sec) * 1000.0 + (stop.tv_usec - start.tv_usec) / 1000.0;
        cout << "AlignedParallelAlgorithm time: " << durationTime << " ms" << endl;

        cout << "----------------------------------------" << endl;
    }

    return 0;
}


/*
Testing matrix size: 64
SequentialAlgorithm time: 26.76 ms
AlignedParallelAlgorithm time: 23.425 ms
----------------------------------------
Testing matrix size: 128
SequentialAlgorithm time: 151.691 ms
AlignedParallelAlgorithm time: 118.113 ms
----------------------------------------
Testing matrix size: 192
SequentialAlgorithm time: 520.768 ms
AlignedParallelAlgorithm time: 413.428 ms
----------------------------------------
Testing matrix size: 256
SequentialAlgorithm time: 1228.14 ms
AlignedParallelAlgorithm time: 941.416 ms
----------------------------------------
Testing matrix size: 320
SequentialAlgorithm time: 2281.76 ms
AlignedParallelAlgorithm time: 1696.76 ms
----------------------------------------
Testing matrix size: 384
SequentialAlgorithm time: 4015.36 ms
AlignedParallelAlgorithm time: 2957.07 ms
----------------------------------------
Testing matrix size: 448
SequentialAlgorithm time: 6401.19 ms
AlignedParallelAlgorithm time: 4567.43 ms
----------------------------------------
Testing matrix size: 512
SequentialAlgorithm time: 9521.88 ms
AlignedParallelAlgorithm time: 6907 ms
----------------------------------------
Testing matrix size: 576
SequentialAlgorithm time: 13423.9 ms
AlignedParallelAlgorithm time: 9844.8 ms
----------------------------------------
Testing matrix size: 640
SequentialAlgorithm time: 17918.1 ms
AlignedParallelAlgorithm time: 13178.7 ms
----------------------------------------
Testing matrix size: 704
SequentialAlgorithm time: 24744.4 ms
AlignedParallelAlgorithm time: 17714.8 ms
----------------------------------------
Testing matrix size: 768
SequentialAlgorithm time: 31435.6 ms
AlignedParallelAlgorithm time: 22935 ms
----------------------------------------
Testing matrix size: 832
SequentialAlgorithm time: 40900.2 ms
AlignedParallelAlgorithm time: 29251.7 ms
----------------------------------------
Testing matrix size: 896
SequentialAlgorithm time: 49891.3 ms
AlignedParallelAlgorithm time: 36272 ms
----------------------------------------
Testing matrix size: 960
SequentialAlgorithm time: 60793 ms
AlignedParallelAlgorithm time: 45113.4 ms
----------------------------------------
Testing matrix size: 1024
SequentialAlgorithm time: 76993.2 ms
AlignedParallelAlgorithm time: 56340.3 ms
----------------------------------------
Testing matrix size: 1088
SequentialAlgorithm time: 91362.9 ms
AlignedParallelAlgorithm time: 66657.3 ms
----------------------------------------
Testing matrix size: 1152
SequentialAlgorithm time: 105595 ms
AlignedParallelAlgorithm time: 81447.8 ms
----------------------------------------
Testing matrix size: 1216
SequentialAlgorithm time: 128611 ms
AlignedParallelAlgorithm time: 94833.9 ms
----------------------------------------
Testing matrix size: 1280
SequentialAlgorithm time: 143671 ms
AlignedParallelAlgorithm time: 101993 ms
----------------------------------------
Testing matrix size: 1344
SequentialAlgorithm time: 165874 ms
AlignedParallelAlgorithm time: 123909 ms
----------------------------------------
Testing matrix size: 1408
SequentialAlgorithm time: 193432 ms
AlignedParallelAlgorithm time: 144180 ms
----------------------------------------
Testing matrix size: 1472
SequentialAlgorithm time: 222095 ms
AlignedParallelAlgorithm time: 165803 ms
----------------------------------------
Testing matrix size: 1536
SequentialAlgorithm time: 247223 ms
AlignedParallelAlgorithm time: 181777 ms
----------------------------------------
Testing matrix size: 1600
SequentialAlgorithm time: 293502 ms
AlignedParallelAlgorithm time: 216739 ms
----------------------------------------
Testing matrix size: 1664
SequentialAlgorithm time: 340922 ms
AlignedParallelAlgorithm time: 246546 ms
----------------------------------------
Testing matrix size: 1728
SequentialAlgorithm time: 378462 ms
AlignedParallelAlgorithm time: 279574 ms
----------------------------------------
Testing matrix size: 1792
SequentialAlgorithm time: 428984 ms
AlignedParallelAlgorithm time: 307074 ms
----------------------------------------
Testing matrix size: 1856
SequentialAlgorithm time: 472750 ms
AlignedParallelAlgorithm time: 347226 ms
----------------------------------------
Testing matrix size: 1920
SequentialAlgorithm time: 526256 ms
AlignedParallelAlgorithm time: 367934 ms
----------------------------------------
Testing matrix size: 1984
SequentialAlgorithm time: 548341 ms
AlignedParallelAlgorithm time: 389371 ms
----------------------------------------
Testing matrix size: 2048
SequentialAlgorithm time: 605815 ms
AlignedParallelAlgorithm time: 439535 ms
----------------------------------------
*/
